package com.base.search.impl;

import com.base.search.ISearch;

/**
 * @author li
 */
public class BinarySearch implements ISearch {

    @Override
    public int search(int[] nums, int target) {
        //[0,length-1]
        int left = 0, right = nums.length - 1;
        // 这里是小于等于
        while (left <= right) {
            //可以防止left+right溢出（超出整数范围)
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                // 中间加一
                left = mid + 1;
            } else if (nums[mid] > target) {
                // 中间减一
                right = mid - 1;
            }
        }
        return -1;
    }

    /**
     *     二分查找的扩展，寻找左侧边界（leetcode 278题查看第一个错误的版本）
      */
    public int left_bound(int[] nums, int target) {
        //注意边界为[0,length]
        int left = 0, right = nums.length - 1;
        //结束条件 left>right
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                right = mid - 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }


        // 最后要检查 left 越界的情况
        if (left >= nums.length || nums[left] != target){
            return -1;
        }
        return left;
    }

    /**
     *     二分查找的扩展，寻找右侧边界
      */
    public int right_bound(int[] nums, int target) {
        //注意边界为[0,length-1]
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        // 最后要检查 right 越界的情况
        if (right < 0 || nums[right] != target)
            return -1;
        return right;
    }

    /**
     *     二分搜索插入
     */
    public int search_insert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int mid = -1;
        //跳出条件为left=right
        while (left < right) {
            mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else if (target > nums[mid]) {
                left = mid + 1;
            }

        }


        return target > nums[left] ? left + 1 : left;
    }

}
